\section{Introduction}

In this document, I propose a new design for wasp's DSL. The description
of the new DSL will be divided into three parts: a formal definition, my
motivation for key decisions, and ideas on its potential implementation.

From here on, the new version of wasp's DSL will be referred to as \strong{wasp}
and the current version as \strong{old wasp}.

\section{Formal Definition}

Wasp is composed of four parts: the syntax, a type system, evaluation method,
and the standard library.

\subsection{Syntax}

\begin{verbatim}
<wasp>    ::= <import>* <stmt>*
<stmt>    ::= <decl> | <defn> | <export>

<decl>    ::= <ident> <ident> <expr>
<defn>    ::= <ident> '=' <expr>
<import>  ::= 'import' <string> 'as' <ident>
<export>  ::= 'export' <ident> (',' <ident>)* from <string>

<expr>    ::= <dict> | <list> | <dot>
            | <string> | <extimport> | <quoter>
            | <ident> | <num> | <bool>
<dict>    ::= '{' <dictentry> (',' <dictentry>)* '}'
            | '{' '}'
<dictentry> ::= <ident> ':' <expr>
<list>    ::= '[' <expr> (',' <expr>)* ']' | '[' ']'

<extimport>  ::= 'import' <name> 'from' <string>
<name>    ::= '{' <ident> '}' | <ident>
<dot>     ::= <expr> '.' <ident>
<quoter>  ::= '{=' <ident> <anything> <ident> '=}'
<bool>    ::= 'true' | 'false'
\end{verbatim}

The \texttt{<anything>} inside \texttt{<quoter>} is ambiguous, so to correctly
parse wasp, a quoter starting with \texttt{\{=tag} must contain all text until
the first \texttt{tag=\}} or until the end of the input.

The nonterminals for strings, numbers, and identifiers are not shown.

\subsection{Type System}

Wasp is a statically typed language. The following inference rules describe the
type system. Some special conventions are followed:

\begin{itemize}
  \item $\tau_i$ and $\sigma_i$ are types
  \item $e_i$ is an expression
  \item \texttt{ki}, \texttt{ji}, \texttt{xi} are identifiers
  \item \texttt{monospace} words are tokens from a wasp file
  \item The syntax $\Gamma = \Gamma, \texttt{x} : \tau$ updates $\Gamma$ such that
        $\texttt{x} : \tau \in \Gamma$
\end{itemize}

\subsubsection{Type Rules}

\begin{mathparpagebreakable}
  \inferrule[Var]{
    \texttt{x} : \tau \in \Gamma
  }{
    \Gamma \vdash \texttt{x} : \tau
  }

  \inferrule[Import]{
    \Gamma_{other} \vdash \texttt{x1} : \tau_1 \\ \ldots \\ \Gamma_{other} \vdash \texttt{xn} : \tau_n
  }{
    \texttt{import "other" as } Q \\
    \Gamma = \Gamma, Q : \{
      \texttt{x1} : \tau_1, \ldots, \texttt{xn} : \tau_n  
    \}
  }

  \inferrule[Export]{
    \Gamma_{other} \vdash \texttt{x1} : \tau_1 \\ \ldots \\ \Gamma_{other} \vdash \texttt{xn} : \tau_n
  }{
    \texttt{export x1, ..., xn from "other"}
  }

  \inferrule[Decl]{
    \Gamma \vdash e : \tau \\
    \texttt{data typeName = } \tau
  }{
    \texttt{typeName x = } e \\
    \Gamma = \Gamma, \texttt{x} : typeName
  }

  \inferrule[Defn]{
    \Gamma \vdash e : \tau \\
  }{
    \Gamma \vdash \texttt{x = } e \\
    \Gamma = \Gamma, \texttt{x} : \tau
  }

  \inferrule[Enum]{
    \texttt{enum enumName = } \ldots \texttt{|} E_i \texttt{|} \ldots
  }{
    \Gamma \vdash E_i : enumName
  }

  \inferrule[Dict]{
    \Gamma \vdash e_1 : \tau_1 \\ \ldots \\ \Gamma \vdash e_n : \tau_n
  }{
    \Gamma \vdash \texttt{\{ k1:} e_1\texttt{,} \ldots\texttt{,} \texttt{kn:} e_n \texttt{\}} :
                  \{ k1: \tau_1, \ldots, kn: \tau_n \}
  }

  \inferrule[DictNone]{
    \Gamma \vdash e : \{ \texttt{k1}: \tau_1, \ldots, \texttt{kn}: \tau_n \}
  }{
    \Gamma \vdash e : \{
      \texttt{k1}: \tau_1, \ldots, \texttt{kn}: \tau_n,
      \texttt{j}: \sigma?
    \}
  }

  \inferrule[DictSome]{
    \Gamma \vdash e : \{ \texttt{k1}: \tau_1, \ldots, \texttt{kn}: \tau_n, \texttt{j}: \sigma \}
  }{
    \Gamma \vdash e : \{
      \texttt{k1}: \tau_1, \ldots, \texttt{kn}: \tau_n,
      \texttt{j}: \sigma?  
    \}
  }

  \inferrule[List]{
    \Gamma \vdash e_1, \ldots, e_n : \tau
  }{
    \Gamma \vdash \texttt{[ } e_1 \texttt{,} \ldots \texttt{,} e_n \texttt{ ]} : [\tau]
  }

  \inferrule[EmptyList]{ }{
    \Gamma \vdash \texttt{[]} : emptyList
  }

  \inferrule[AnyList]{
    \Gamma \vdash e : emptyList
  }{
    \Gamma \vdash e : [\tau], \forall \tau
  }

  \inferrule[Dot]{
    \Gamma \vdash e : \{ \texttt{k}: \tau, \ldots \}
  }{
    \Gamma \vdash e\texttt{.k} : \tau
  }

  \inferrule[String]{ }{\Gamma \vdash \texttt{"string"} : string}

  \inferrule[Number]{ }{\Gamma \vdash \texttt{3.14} : number}

  \inferrule[ExtImport]{ }{
    \Gamma \vdash \texttt{import ImportName from "file"} : import \\
    \Gamma \vdash \texttt{import { importName } from "file"} : import
  }

  \inferrule[Quote]{ }{
    \Gamma \vdash \texttt{\{=quot } \ldots \texttt{ quot=\}} : quot
  }
\end{mathparpagebreakable}

\textsc{DictNone} allows omitting optional entries from a dictionary, and
\textsc{DictSome} allows including optional entries.

An ambiguity that arises is whether \texttt{x = [\{a: 1\}, \{\}]} is well-typed,
and if \texttt{x}'s type is $[\{\}]$ or $[\{ a: number? \}]$.

The rules \textsc{EmptyList} and \textsc{AnyList} are one way of allowing empty
lists to type check, since \textsc{List} does not allow picking a type for an
empty list. An alternative would be allowing type variables to be given to any
ambiguous expressions, like an empty list, and having a separate pass to resolve
the ambiguities from surrounding context. The current method for checking empty
lists was chosen as it gives a much simpler implementation.

\subsubsection{Type Checking}

There are two phases to the type checker:

\begin{enumerate}
  \item Imported files are type checked, then the \textsc{Import}
        rule is applied.
  \item Binding declaration types: The conclusion of \textsc{Decl} is assumed
        for all \texttt{<decl>}s, essentially forward declaring each of them.
  \item Type checking of statements:
        \begin{enumerate}
          \item \textsc{Defn}, \textsc{Export} and the premise of \textsc{Decl}
                are checked against statements in their lexical order.
          \item Quoted text (ex. \texttt{\{=json [1] json=\}}) is parsed.
          \item Recovery should be attempted on a type error, to allow reporting
                of multiple errors per compilation.
        \end{enumerate}
\end{enumerate}

\subsection{Evaluation}

Since wasp has no control flow, evaluation is simple. Definitions must be
evaluated in order. The evaluation order of declarations is left
unspecified. When declarations are evaluated, so are their arguments.

Only the values of declarations are visible to the caller of the wasp
interpreter.

\subsubsection{Imports and Exports}

At the beginning of a wasp file, a list of import statements is allowed. When
a wasp file is imported into another, it is evaluated before the importer. The
\textsc{Import} rule is used for type checking. 

\texttt{import "other.wasp" as Q} binds the variables and declarations from
other.wasp to a variable \texttt{Q} in the current file.

Note that expressions in other.wasp can not refer to any
bindings in the importer.

Exports are related to imports. You can re-export bindings from another wasp
file. \textsc{Export} is the rule used for type checking these statements. All
that is required is that the binding exist, which means exporting bindings
created by definitions is possible (in the type system). This action will cause
an evaluation-time error.

\subsection{Standard Library}

Described below is the standard library for wasp. The syntax of the definitions
here are the same as used in the type rules.

\begin{verbatim}
enum authMethod = UsernameAndPassword
enum paramType = StringParam | NumberParam

data app = { title : string
           , auth : { userEntity : entity
                    , methods : [authMethod]
                    , onAuthFailedRedirectTo : route
                    }
           , dependencies : json
           }
data page = { component : import
            , authRequired : bool?
            , params : [{ name : string, paramType : paramType }]?
            }
data entity = psl
data query = { fn : import, entities : [entity] }
data action = { fn : import, entities : [entity] }
data route = { path : string
             , page : page
             }
\end{verbatim}

\section{Motivation}

The four main things considered in the design of wasp are:

\begin{enumerate}
  \item Similarity to old wasp
  \item Safety
  \item Extensibility
  \item Simplicity
\end{enumerate}

For more context on revisions of this proposal, see
\href{https://github.com/wasp-lang/wasp/issues/109}{Issue \#109}.

\subsection{Similarity to old wasp}

This was the driving force for this design. Old wasp is very clear to read and
works well for its purpose. Wasp is mostly a formalized version of old wasp.

Not counting new features, the two DSLs are very similar. When translating
from old wasp to wasp, only the following changes must be kept in mind:

\begin{itemize}
  \item \texttt{route}s are now named
  \item \texttt{page} has an optional \texttt{params} parameter to specify
        path parameters
  \item The \texttt{onAuthFailedRedirectTo} field in \texttt{auth} now requires
        a \texttt{route} instead of a string
  \item \texttt{authentication} and \texttt{dependencies} are now fields in the
        \texttt{app} declaration.
\end{itemize}

\subsection{Safety}

The type system introduces new mechanisms for safely writing wasp
configurations: \texttt{route} was changed to a declaration to allow for
type safe URLs; \texttt{page} specifies path parameters so that, in the future,
a typescript codebase could generate types for path parameters.

\subsection{Extensibility}

Defining wasp's configuration objects in types instead of as syntax will make
it easier for maintainers to add new objects to wasp. In old wasp's
implementation, a custom parser had to be written for each type. Now, a
developer just needs to declare a new type in the wasp library. A suggestion
for how this might look is described in section 4.2.

Additionally, having all wasp objects described through the same mechanism will
make it more worth the effort to develop a detailed error system for more
helpful syntax and type errors when compiling a wasp project.

Finally, wasp's flexibility makes possible a plugin system to add more features
to wasp without bloating its core library.

\subsection{Simplicity}

While wasp is much more complex than old wasp, it is still fairly simple.
Notably, control flow is absent. I wanted wasp to be as simple as possible
to make experimenting with its implementation less painful. Hopefully, when
a good implementation is found, it will be flexible enough to bring
in more complex features as needed.

\section{Implementation Suggestions}

The following sections describes my ideas for parts of the implementation of
wasp.

\subsection{Parsing}

\href{https://github.com/wasp-lang/wasp/issues/109}{Issue \#109} has good notes
about parsing, but I think the best option would be a parser generator (Happy
is mentioned in the issue). Writing a parser by hand, even with a parser
combinator library, seems wasteful when there is a formal grammar available.
On the other hand, parser combinators have the advantage of being able to
directly produce a structure most convenient for the next phases.

\subsection{Type checking}

The actual strategy of type checking should be relatively simple. There are no
polymorphic types or type inference of recursive definitions, thus no constraint
solving is necessary to verify the program. This should make the type of each
expression and statement easy to check.

I instead want to focus on defining types in wasp. It seems very possible that
non-primitive types could be defined and used in the following way (omitting
language extensions and imports):

\begin{minipage}{\linewidth}
\begin{lstlisting}
data ParamType = StringParam | NumParam
                 deriving (Generic)
newtype PageParam = PageParam { name :: String
                              , paramType :: ParamType
                              } deriving (Generic)
newtype Page = Page { component :: Analyzer.Primitive.Import
                    , authRequired :: Maybe Bool
                    , params :: Maybe [PageParam]
                    } deriving (Generic)

interpretWithLib :: String -> Either Analyzer.Error [Analyzer.Decl]
interpretWithLib = Analyzer.interpret $ do
  Analyzer.registerEnumType @ParamType
  Analyzer.registerDataType @Page

-- To use pages declared by a wasp file
printPageComponents :: Analyzer.Result -> IO ()
printPageComponents decls = do
  let pageDecls = Analyzer.Decl.take @Page $ decls
  mapM_
    (\(name, page) -> putStrLn $ name ++ ": " ++ show (component page))
    pageDecls
\end{lstlisting}
\end{minipage}

\texttt{registerEnumType} and \texttt{registerDataType} would all be
implemented using GHC generics. Additionally, some type classes would be used
to only allow types in specific forms:

\begin{minipage}{\linewidth}
\begin{lstlisting}
-- `IsWaspEnum` ensures `a` is in the form `data A = A1 | ... | An`
registerEnumType :: (Generic a, IsWaspEnum a) => WaspMonad ()
-- `IsWaspType` ensures `a` has one constructor that either:
--   - Has one parameter
--   - Uses record syntax
--  And only contains:
--   - Wasp primitives
--   - Maybes, Lists
--   - IsWaspEnums
--   - IsWaspTypes
registerDeclType :: (Generic a, IsWaspType a) => WaspMonad ()
\end{lstlisting}
\end{minipage}

An important function is \texttt{Analyzer.Decl.take}, which extracts a specific
type from the existentially quantified type \texttt{Decl}:

\begin{minipage}{\linewidth}
\begin{lstlisting}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE TypeApplications #-}
import Data.Typeable (Typeable, cast)
import Data.Maybe (mapMaybe)

data Decl where
  Decl :: (Typeable a) => String -> a -> Decl

take :: (Typeable a) => [Decl] -> [(String, a)]
take = mapMaybe $ \case
  Decl x -> cast x
\end{lstlisting}
\end{minipage}

\subsection{Evaluation}

Evaluation of definitions is simple, just compute them in order. Imports also
are pretty intuitive. In case of a cyclical import path, an evaluation time
error will be generated. Exports are very straightforward, but some care should
be taken to avoid evaluating a wasp file twice when both importing and
exporting it.

Evaluating declarations is a bit more nuanced, since they can refer to
declarations declared lexically after themselves. One possible solution is to
sort the declarations topographically before evaluation. This poses a problem
for mutually recursive declarations, since no traversal order of a cyclical
graph will work.

Alternatively, time travel could be used to make the final results of
evaluation available to every single declaration, which solves
the circular reference problem. If unfamiliar with time travel in Haskell, read
\href{https://blog.csongor.co.uk/time-travel-in-haskell-for-dummies/}{this article}
for an introduction. This may have performance consequences.

Another interesting part is what structure to store the evaluated result in.
Following from 4.2, it makes sense to use the registered ADTs as the result
types. \texttt{Data.Data} seems to be the module to use for this.

The \texttt{Data.Data} allows constructing values of arbitrary constructors.
If type checking succeeds, we can then create the proper data types to return.
I have investigated the \texttt{Data.Data} module and I am confident this will
work, but \texttt{unsafeCoerce} might be needed.

\section{Closing Thoughts}

This is not a finished design. It definitely needs more work before
implementing it, especially because its implementation will take a lot of work
and require changes across the existing code base.

Because this implementation is quite large, I think it would make the most
sense to start by defining its API and the boundaries between the three systems
of the DSL. Then, the implementation could be divided into three
sub-projects.
